1. Field of the Invention
The present invention relates to a two dimensional object layout apparatus for automatically designing a two-dimensional layout of many objects such as commodities in a warehouse, parts on a printed circuit board, or cells on a VLSI (Very Large Scale Integration) circuit, and a method thereof.
2. Description of the Related Art
In designing a printed circuit and a VLSI, a very large number of circuit parts, transistors, and so forth should be laid out on a two-dimensional board (or a chip). To do that, computer aided design (CAD) systems have been used.
Such CAD systems roughly operate in two phases. The first phase is a logical phase where logic circuits are formed, a process is simulated, and test data is generated. The second phase is a physical phase where cells (parts) are laid out and lines (leads) thereof are connected.
In the second phase, based on a design drawing of a logic circuit received from the first phase, a large number of circuit elements or semiconductor devices are optimally laid out on a two-dimensional plane (of multiple layers) and lines thereof are optimally connected corresponding to a predetermined design rule for each device and therebetween in such a manner that the total area of the structure becomes compact and the line lengths become short.
In the process for laying out cells, it is not effective to directly handle cells in the order of the 0.1 million cells or 1 million cells of an VLSI. Thus, conventionally, the physical design work is hierarchically performed and thereby several tens of cells to several hundreds of cells (module parts) are handled at a time. Each cell has the size and shape necessary for the internal logic and the input/output terminals. These cells should be connected with lines corresponding to the logical design. However, unless the layout of the cells is designated, wiring is not determined.
A fundamental problem for laying out cells is to optimally obtain a two-dimensional layout of cells of various sizes (mainly, rectangular cells) free from two-dimensionally overlapping in consideration of the line connections among them. The optimization of this layout is a problem in which the degree of freedom of the search space is very large. Thus, a highly heuristic solution is required.
The method that has been widely used for easily designing a layout is the standard cell method (gate array method). In this method, the lengths of individual cells are regulated and many cells are laid out breadthwise. Input/output terminals of the cells are laid out lengthwise only. When the lengths of the cells are restricted and the layout positions thereof are restricted, the degree of freedom of the two dimensional layout problem is reduced.
When cells are two-dimensionally laid out without restricting the sizes and shapes thereof, a problem for laying out many rectangles in a two-dimensional container (for example, a circuit base board or a chip) as compactly as possible needs to be solved. Thus, this problem is referred to as xe2x80x9ca problem for optimizing a two-dimensional layout of rectangles.xe2x80x9d
As one method for optimizing a two-dimensional layout of rectangles, Otten et al. has proposed the xe2x80x9cSlicing floorplanxe2x80x9d method (R. H. J. M Otten, xe2x80x9cAutomatic Floorplan Design, in Proc. 19th ACM/IEEE Design Automation Conf., pp. 261-267, 1982). In this method, one rectangular base board is sliced lengthwise or breadthwise into two portions at a suitable position. Each of the sliced portions is further sliced into two portions. This process is repeated.
A two-branched tree that represents such division is formed as a data structure. By laying out individual cells to branches, the required area is obtained. By varying the dividing method (a combination of lengthwise and breadth wise slicing), the minimum area is obtained. A drawback of this method is in that rectangles cannot be laid out in a chained pattern.
In addition, Nakatake et al. has proposed the BSG (Bounded Slicing Grid) method for optimizing a two-dimensional layout of rectangles (S. Nakatake, K. Fujiyoshi, H. Murata, Y. Kajitani, xe2x80x9cModule Placement on BSG-Structure and IC Layout Applications,xe2x80x9d Int. Conf. on Computer Aided Design, 1996). In this method, cells are laid out on grids with a special structure termed a BSG. The cells are mapped to a physical space corresponding to the rules of BSG method.
The BSG method represents a restriction in which cells are laid out lengthwise and breadth wise adjacent to the positions of the BSG grids. Since this restriction is strict, blanks are inserted at suitable positions on the grids to obtain a more compact layout. To optimize the layout of the cells, trial and error is repeated in laying out cells in the BSG and an optimum result is selected.
In the aforementioned standard cell method, slicing floorplan method, and BSG method, as a common process, various layouts are simulated and an optimum result is obtained. When this trial and error process is manually performed, huge amounts of work are required.
To solve this problem, with a proper evaluation function, the simulation is performed as effectively and systematically as possible. To do that, a conventional optimizing method can be used. As such a conventional method, the simulated annealing (SA) method has become popular.
In the SA method, the optimizing search space is represented with parameters. By a converting operation with parameters including a probability element, a desired solution is searched for by trial and error. In the SA method, it is important to consider how search parameters are structured for the problem they are to be applied to, (in this case a problem of a two-dimensional layout of rectangles), and when a particular parameter is given, how the given parameter is converted into a particular space (namely, laid out two-dimensionally) and how the obtained result is evaluated.
These points should be considered for individual problems and solutions. In reality, the optimization by the SA method has been attempted with the standard cell method, slicing floorplan method, and BSG method.
However, the aforementioned conventional solving methods have the following drawbacks.
In the standard cell method, so as to simplify a given problem, the lengths of cells and the two-dimensional layout thereof are restricted. According to this method, although the problem is simplified, it is not assured that wiring among the cells are optimum. It is logically clear that when such restrictions are not applied, better layout results can be obtained.
In the slicing floorplan method, since the slicing in two process is repeated, special layouts such as a four-rectangle-chained shape cannot be represented. Although a modification method for representing such a shape has been studied, complicated calculations are required.
In the BSG method, the structure of the grids is special and complicated. In addition, the restrictions are strict. In other words, unless many blanks are inserted on the grids, cells cannot be freely laid out. Thus, the BSG method is used for automatically optimizing a layout of cells corresponding to the SA method, rather than creating a BSG that represents a two-dimensional layout by a designer. Although good results from calculations in the SA method have been obtained at the laboratory level, they should be further improved for practical use.
As described above, although many CAD tools for two-dimensional layouts have been developed and used, with respect to calculation time and quality thereof, there are still many problems to be solved.
In the designing phase of a cell layout for a VLSI that requires high performance, it is stated that a manual layout performed by an experienced designer is superior to an automatic layout. In addition, as the structure and scale of the VLSI have become complicated and large and the required design period has become short, a new approach for solving the problem of a two-dimensional layout has been strongly desired.
An object of the present invention is to provide a two-dimensional layout apparatus for accurately and promptly solving such a two-dimensional layout problem and a method thereof.
A first aspect of the present invention is a two-dimensional layout system having a storing unit and a layout unit for designing a layout of a plurality of objects. The objects are any physical resources that have shapes and sizes.
The storing unit stores a priority rule for layout positions. The layout unit determines the layout positions of the objects in a layout space according to the priority rule for the layout positions. The priority rule for the layout positions represents a predetermined rule for determining priority layout positions of objects in the current layout space.
A second aspect of the present invention is a two-dimensional layout system having a space representing unit and a managing unit. The space representing unit represents a two-dimensional space composed of at least one closed figure surrounded by lengthwise sides and breadthwise sides with a set of inscribed rectangles, a part of each side of which is included in a side of the closed figure. The managing unit manages the two-dimensional space with the set of inscribed rectangles.
A third aspect of the present invention is a reverse analyzing apparatus having a storing unit and an analyzing unit. The storing unit stores a priority rule for layout positions. The analyzing unit analyzes a layout result of a plurality of objects, and obtains a layout order for objects to restore the layout result by laying out the objects according to the priority rule for the layout positions.
A fourth aspect of the present invention is a layout evaluating apparatus having a layout unit and an evaluating unit for designing a layout of a plurality of objects. Whenever an object is received, the layout unit determines the layout position of the received object in a layout space according to the priority rule for the layout positions. The evaluating unit evaluates the layout result obtained by the layout unit.
A fifth aspect of the present invention is a layout optimizing apparatus having a storing unit, a layout unit, and an evaluating unit for designing a layout of a plurality of objects. The storing unit stores a priority rule for layout positions. Whenever an object is received, the layout unit determines the layout position of the received object in a layout space, which is defined by excluding other objects that have been laid out from an initial space, according to the priority rule for the layout positions. The evaluating unit evaluates a plurality of layout results obtained by varying at least one of the object layout order, the priority rule for the layout positions, and the initial space, and selects an excellent layout result.
A sixth aspect of the present invention is a layout optimizing apparatus having a storing unit, a layout unit, an evaluating unit, and a searching unit based on the simulated annealing method for designing a layout of a plurality of objects.
The storing unit stores at least one priority rule for layout positions. Whenever an object is received, the layout unit determines the layout position of the received object in a layout space according to the priority rule for the layout positions. The evaluating unit evaluates the layout result obtained by the layout unit. The searching unit represents the object layout order as a parameter of the search space. While varying the parameter according to the simulated annealing method, the searching unit searches the search space and automatically obtains an excellent layout result.
A seventh aspect of the present invention is a layout optimizing apparatus having a storing unit, a layout unit, an evaluating unit, and a searching unit based on a genetic algorithm for designing a layout of a plurality of objects.
The storing unit stores at least one priority rule for layout positions. Whenever an object is received, the layout unit determines the layout position of the received object in a layout space according to the priority rule for the layout positions. The evaluating unit evaluates the layout result obtained by the layout unit. The searching unit represents the object layout order as gene data, performs a genetic operation for a gene group including at least one gene data according to the genetic algorithm, and automatically obtains an excellent layout result.